Flip game

Time: O(CxN + N) = O(Nx(C+1)); Space: O(N); easy

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–”. The game ends when a person can no longer make a move and therefore the other person will be the winner. Write a function to compute all possible states of the string after one valid move.

Example 1:

Input: s = “++++”

After one move, it may become one of the following states: Output:

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].

class Solution1(object):
    """
    This solution compares only O(1) times for the two consecutive "+"
    Time: O(C*N + N) = O(N*(C+1)); Space: O(N)
    """
    def generatePossibleNextMoves(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        i, n = 0, len(s) - 1

        while i < n:                                    # O(N) time
            if s[i] == '+':
                while i < n and s[i+1] == '+':          # O(C) time
                    res.append(s[:i] + '--' + s[i+2:])  # O(N) time and space
                    i += 1
            i += 1

        return res

sol = Solution1()
s = "++++"
assert sol.generatePossibleNextMoves(s) == ['--++', '+--+', '++--']

class Solution2(object):
    """
    This solution compares O(M) = O(2) times for two consecutive "+", where M is length of the pattern
    Time: O(C*M*N + N) = O(C*N + N), where M = 2 in this question; Space: O(N)
    """
    def generatePossibleNextMoves(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        return [s[:i] + "--" + s[i+2:] for i in range(len(s) - 1) if s[i:i+2] == "++"]

sol = Solution2()
s = "++++"
assert sol.generatePossibleNextMoves(s) == ['--++', '+--+', '++--']

See also:

https://leetcode.com/problems/flip-game

https://www.lintcode.com/problem/flip-game